1. Field of the Invention
The present invention generally relates to logical operation circuits, and more particularly to a logical operation circuit related to a Wallence tree circuit used for an operation such as a multiplying operation in order to speed up the operation in a computation unit.
2. Description of the Prior Art
A Wallence tree circuit is conventionally employed in a computation unit such as a computer in order to speed up the operation of a logical operation unit such as a multiplier.
FIG. 1 is a block diagram of an adder having a Wallence tree circuit used for multiplication. The Wallence tree adder shown in FIG. 1 performs an adding operation on seven operands, each of which consists of N bits (digits) where N is an arbitrary integer. The circuit shown in FIG. 1 includes N adders 21.sub.1 -21.sub.N, and a single adder 22 such as a carry propagation adder (usually abbreviated as CPA). The N adders 21.sub.1 -21.sub.N respectively correspond to the N digits, and perform adding operations on the respective digits. Then, the adders 21.sub.1 -21.sub.N output sum signals and carry signals. For example, the adder 21.sub.1 performs the adding operation on first digits D1.sub.1 -D7.sub.1 of the seven operands, and outputs a sum signal SUM.sub.1 and a carry signal CRY.sub.1. A plurality of carry signals or bits are generated in the operation of the adder 21.sub.1, and are applied to the adder 21.sub.2. The adder 21.sub.2 utilizes the received carry signals in its own adding operation. The adder 22 receives the sum signals SUM.sub.1 -SUM.sub.N and carry signals CRY.sub.1 -CRY.sub.N from the adders 21.sub.1 -21.sub.N, respectively, and outputs operation results S.sub.1 -S.sub.N.
FIG. 2 is a block diagram of the structure of each of the adders 21.sub.1 -21.sub.N. For the convenience sake, FIG. 2 shows a structure related to the nth digit and the (n+1)th digit where 1&lt;n and n+1&lt;N). As shown in FIG. 2, each of the adders 21.sub.1 -21.sub.N includes a Wallence tree circuit in which a plurality of one-bit full adders FA1 are connected so as to form a tree. Each of the full adders FA1 has three inputs and two outputs. The above tree structure improves the adding operation and the operation speed, as compared with an ordinary sequential operation in which an operand is added to the result of an operation on which two operands are added.
The structure shown in FIG. 2 has four stages of full adders FA1 extended in the signal propagating direction. This structure makes a seven-input/two-output circuit configuration. For example, the structure receives the seven inputs D1.sub.n -D7.sub.n and outputs two outputs SUM.sub.n and CRY.sub.n. The carry signals generated at the respective stages except for the final stage are propagated to the next digit. For example, four carry signals generated at the (n-1)th digit are applied to three full adders FA1 of the nth digit, as shown in FIG. 2.
FIG. 3 is a block diagram of the three-input/two-output one-bit full adder FA1 used to form the adders 21.sub.1 -21.sub.N. The full adder FA1 is made up of two exclusive-OR (EX-OR) circuits 11 and 12, and three NAND circuits 13, 14 and 15. Inputs DIN1, DIN2 and DIN3 are applied, as shown in FIG. 3. The sum result SUM and the carry CRY are respectively output from the exclusive-OR circuit 12 and the NAND circuit 14. For example, when DIN1=DIN2=DIN3=1, then SUM=1 and CRY=1. When DIN1=DIN2=1, and DIN3=0, then SUM=0 and CRY=1. As described above, the full adder FA1 is of a positive-logic input/positive logic output type.
However, the above-mentioned prior art has the following disadvantages.
Normally, 32 field effect transistors are needed to form the one-bit full adder FA1 by CMOS circuits. More particularly, each of the exclusive-OR circuits 11 and 12 is made up of 10 transistors, and each of the three NAND circuits 13-15 is made up of four transistors. The Wallence tree circuit uses a plurality of full adders FA1 as described above, and has a large circuit size. The multiplier is mostly configured by Wallence tree circuits as shown in FIG. 1, and needs a large area on a chip.
The critical path of the full adder FA1 includes the exclusive-OR circuit 11, the NAND circuit 13 and the NAND circuit 14. It takes a long time for a signal to be propagated through the critical path. The Wallence tree circuit utilizes a plurality of full adders as described above, and thus a large delay occurs therein.